package _01_第一季.栈与队列03;

import _01_第一季._00_公共接口.Deque;

public class ArrayLoopDeque<E> implements Deque<E>{
    private int size;
    private E[] elements;
    private int front; //指向队头元素
    private static final int DEFAULT_CAPACITY = 10;

    public ArrayLoopDeque(){
        elements = (E[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        size = 0;
    }
    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    private int index(int index){
        index += front;
        if(index<0){
            return index + elements.length;
        }
        return index - (index>= elements.length ? elements.length : 0);
    }

    //从队尾进入
    @Override
    public void enQueueRear(E element) {
        ensureCapacity(size+1);
        elements[index(size)] = element;
        size++;
    }

    //从队头出
    @Override
    public E deQueueFront() {
        E ret = elements[front];
        elements[front] = null;
        front = index(1);
        size--;
        return ret;
    }

    //从队头入队
    @Override
    public void enQueueFront(E element) {
        ensureCapacity(size+1);
        front = index(-1);
        elements[front] = element;
        size++;
    }

    //从队尾出队
    @Override
    public E deQueueRear() {
        int lastIndex = index(size-1);
        E ret = elements[lastIndex];
        elements[lastIndex] = null;
        size--;
        return ret;
    }

    @Override
    public E front() {
        return elements[front];
    }

    @Override
    public E rear() {
        return elements[index(size-1)];
    }

    @Override
    public void clear() {
        for(int i=0;i<size;++i){
            elements[index(i)] = null;
        }
        size = 0;
        front = 0;
    }
    //动态扩容
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length; //原来的容量
        if(oldCapacity >= capacity) return; //如果原来的容量够，直接返回

        //新容量为原来的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for(int i=0;i<size;++i){
            newElements[i] = elements[index(i)]; //保证找到原数组front
        }
        //重新指向
        elements = newElements;
        front = 0; //改变队头指针的位置
    }
}
